package com.example.leetcode.trainingcamp.week5.Thursday;

/**
 * 367. 有效的完全平方数 给定一个 正整数 num ，编写一个函数，如果 num 是一个完全平方数，则返回 true ，否则返回 false 。
 *
 * <p>进阶：不要 使用任何内置的库函数，如 sqrt 。
 *
 * <p>示例 1：
 *
 * <p>输入：num = 16 输出：true 示例 2：
 *
 * <p>输入：num = 14 输出：false
 */
public class Test367 {

    public boolean isPerfectSquare(int num) {
        int high = num;
        int low = 1;
        double sqrt = Math.sqrt(Integer.MAX_VALUE);
        while (low<=sqrt){
            int mid = low + (high - low) / 2; //得到中间值
            if ((long)mid * mid == num) return true;
            if ((long)mid * mid > num){
                if ((long)(mid-1) * (mid-1) <num) return false;
                else if ((long)(mid-1) * (mid-1) == num) return true;
                else {
                    high = mid -1;
                }
            }
            if ((long)mid * mid <num){
                if ((long)(mid+1) *(mid+1) >num) return false;
                else if ((long)(mid+1) *(mid+1) == num) return true;
                else low = mid +1;
            }
        }
        return false;
    }
}


class Demo367{
  public static void main(String[] args) {
    int nums = 808201;
    Test367 t = new Test367();
    System.out.println(t.isPerfectSquare(nums));
  }
}